/*
 * @lc app=leetcode.cn id=133 lang=cpp
 *
 * [133] 克隆图
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    Node *cloneGraph(Node *node, unordered_map<Node *, Node *>& visited)
    {
        if (node == NULL)
            return NULL;
        if (visited.find(node) == visited.end())
        {
            Node *root = new Node(node->val);
            root->neighbors = vector<Node *>();
            visited[node] = root;
            for (auto n : node->neighbors)
            {
                root->neighbors.push_back(cloneGraph(n, visited));
            }
            return root;
        }
        return visited[(node)];
    }
    Node *cloneGraph(Node *node)
    {
        if (!node)
            return NULL;
        unordered_map<Node*, Node*> visited;

        return cloneGraph(node, visited);
    }
};
// @lc code=end
